Інститут менеджменту та економіки „Галицька Академія” Кафедра програмного забезпечення та штучного інтелекту КУРСОВА РОБОТА з дисципліни: “Основи дискретної математики” Тема – Розв’язання задач з елементів теорії алгоритмів та моделей обчислювання і за допомогою машин Тюрінга. ПОЯСНЮВАЛЬНА ЗАПИСКА м. Івано-Франківськ 2004  Анотація В курсовій роботі проаналізовані основні поняття і властивості елементів теорії алгоритмів, функціонування моделей обчислювання та функціонування машин Тюрінга, і розв’язання певних типів задач. Summary In the term paper there are the analysed basic concepts and properties of elements of theory of algorithms, functioning of models of calculation and functioning of machines of Tjuringa. ЗМІСТ Вступ 1. Алгоритм Евкліда. 2. Властивості алгоритмів. 3. Універсальна машина Тюрінга. .......................................................... 3.1 Проблема зупину. ....................................................................... 3.2 Теза Тюрінга. Зв’язок рекурсивних функцій з машинами Тюрінга. ............................................................................................. 3.4 Алгоритмічна нерозв’язуваність і машини Тюрінга. .............. 4. Задача по теорії алгоритмів.......................................................... 5. Задачі по машинах Тюрінга. ........................................................ Висновок Перелік використаних літературних джерел.......................... Вступ З давніх часів у математиці склалося інтуїтивне уявлення про алгоритм як формальне розпорядження, що визначає сукупність операцій і порядок їх виконання для розв’язання задач деякого типу. Термін походить від латинізованої вимови (Algorithmi) імені середньовічного узбецького математика аль-Хорезмі, який ще в ІХ ст. сформулював правила, що дають змогу складати та розв’язувати квадратні рівняння. З алгоритмами, тобто ефективними процедурами, які однозначно приводять до результату, математика мала справу завжди й у своєму розвитку на копичила безліч різних алгоритмів. Дістаючи відповідну інтерпретацію в конкретних додатках, вони становлять значну і найсуттєвішу частину математичного апарату, який використовується в техніці. Відомі зі шкільної програми методи множення <<стовпчиком>> та ділення <<кутом>>, алгоритм Евкліда знаходження найбільшого спільного дільника двох додатних натуральних чисел. Алгоритм Евкліда Нехай задано цілі числа a і b. Знайти їх НСД. 1. Розглянути числа a і b. Перейти до наступного кроку. 2. Порівняти числа a і b (a = b; a > b; a < b). Перейти до наступного кроку. 3. Якщо a = b, то кожне з них є НСД. Кінець. Якщо ні, то перейти до наступного кроку. 4. Якщо a < b,то переставити їх місцями a > b і перейти до наступного кроку. 5. Знайти b- a і розглянути числа a – b. Перейти до кроку 2, і т. доки не дістанеться шуканий результат. Алгоритм Евкліда задано за допомогою найпростіших арифметичних операцій (віднімання, порівняння). Якщо розв’язування якої-небудь задачі зводиться до арифметичних дій, то відповідні алгоритми називають числовими. Алгоритм Евкліда – числовий. Поки математика мала справу в основному з числами й обчисленнями, а поняття алгоритму ототожнювалися з поняттям методу обчислення, необхідності у вивченні самого поняття розвитку загальної математики алгоритму не виникало. Традиції організації обчислень складалися віками і стали складовою частиною наукової культури в тій самій мірі, що й елементарні навички логічного мислення. У своєму накопичила величезну кількість алгоритмів, але все різноманіття обчислень...